//
// Created by Administrator on 2021/11/16.
// May Saint Diana bless you!
//
#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

class Solution {
public:
    unordered_map<int, vector<int> > mp;

    vector<int> beautifulArray(int N) {
        return f(N);
    }

    /**
     * 分治
     * 精彩！
     * 如果{ X, Y, Z }是一个漂亮数组，则{ k * X + b, k * Y + b, k * Z + b } 也一定是漂亮数组
        奇数 + 偶数 = 奇数 一定成立

        对于一个正整数 N, 我们将其等分为两部分，left和right，
        如果left部分是漂亮数组，right部分也是漂亮数组，
        同时left部分全部是奇数，right部分全部是偶数，
        那么此时left + right组成的数组一定也是一个漂亮数组。

        所以可以采用分治算法，自顶向下
        先将数组分为两部分，将奇数放在left，偶数放在right
        同时保证left和right都是漂亮数组
        递归...

     * @param N
     * @return
     */
    vector<int> f(int N) {
        vector<int> ans(N, 0);
        int t = 0;
        if (mp.find(N) != mp.end()) {
            return mp[N];
        }
        if (N != 1) {
            for (auto x : f((N + 1) / 2)) { // 递归出来的也是漂亮数组
                ans[t++] = 2 * x - 1; // 奇数  放左边
            }
            for (auto x : f(N / 2)) {
                ans[t++] = 2 * x; // 偶数  放右边
            }
        } else {
            ans[0] = 1;
        }
        mp[N] = ans;
        return ans;
    }
};

int main() {
    Solution solution;
    vector<int> ans = solution.beautifulArray(4);
    for (const int &x:ans) cout << x << endl;
    return 0;
}


